模拟赛题解/2025.8.23 模拟赛

T1-亲爱的（habibi）

题面

统计一个字符串 $S$ 中共有多少个子序列，满足：

• 长度为 $6$。
• 前 $4$ 个字符两两不同。
• 第 $3$ 个字符与第 $5$ 个字符相同。
• 第 $4$ 个字符与第 $6$ 个字符相同。

答案对 $998244353$ 取模。

$1\leq|S|\leq10^6$，$S$ 中仅包含大小写英文字母和数字。

题解

考虑设计 dp。

设计状态 $f_{i,len,j,k}$ 表示从位置 $i$ 开始且必定选择 $i$，形成形如 $jkjk$ 的长为 $len$ 的后缀的方案数。

首先 $j,k$ 必有一个为 $S_i$，可以使用滚动数组降一维，记录当前左边每个数剩余的数量，容斥可以得出左半部分的方案数。

复杂度为 $O(|S||\sum|)$。

T2-收藏（collect）

题面

有一个长度为 $k_i$ 的序列，每次可以从最左端和最右端取出一个数，并放在当前已取出的数列的末尾。

共有 $n$ 个序列，要求对每个序列求出最后得到的数列的最长可能 LIS。

$1\leq n,k_i,\sum k_i\leq10^6,1\leq a_{i,j}\leq10^9$。

题解

可以发现操作过程本质上是将序列划分成两段，将后缀翻转后归并两个序列。

在划分序列后，LIS 的上界已然确定，是所有得到的序列的 LIS 长度之和，因为若总 LIS 长度更大，其位于这 $2n$ 个子序列中的部分必然有一个的长度超过该子序列 LIS， 矛盾。

达到这个上界是简单的，只需将求得的子序列 LIS 归并起来。进一步，发现序列的贡献是独立的，只用对每个序列都找到最优划分。

暴力枚举划分并计算左右两段 LIS 显然无法通过。发现瓶颈在于反复计算前后缀 LIS，考虑先通过扫描线+BIT 和指针的方式先处理出每个前后缀的 LIS 长度及 LIS 中离当前位置最近的数，再枚举划分并求得最优位置，找出前后缀 LIS。序列之间的归是简单的。

复杂度为 $O(M\log M)$。

T3-棋盘（chess）

题面

有一个 $n\times m$ 的棋盘，双方轮流放黑白子。

每有一行或一列不完全相同，玩家得一分，每有一行或一列完全相同，对手得一分。

最终若玩家分数为奇数且对手分数为偶数则玩家胜利，否则对手胜利。

求最终能让玩家获胜的棋盘状态得方案数。

$2\leq n,m\leq10^6$。

题解

可以发现你获得的分数和 AI 获得的分数相加等于 $n+m$。则 $n+m$ 为偶数时，一定不存在合法解。又因为当 $n+m$ 为奇数时，若你获得的分数是偶数，那么 AI 一定是奇数，反之亦然。故两者一一对应，只需要求出其中一种方案数即可。

一整行或一整列颜色不完全相同的情况难以处理，所以考虑处理一整行或一整列颜色完全相同的情况。即现在需要解决这个问题：一整行或一整列颜色完全相同的数量是偶数的方案数。再反过来，先考虑为奇数的方案，再用总方案去减。

根据惯用做法，直接容斥/二项式反演。先考虑容斥系数的求解：对于答案至少有 $i$ 个产生贡献的情况，恰好 $i$ 是最后一次计算。

• 当答案至少有 $0$ 个产生贡献时：容斥系数为 $0$。
• 当答案至少有 $1$ 个产生贡献时：之前产生 $\binom{1}{0}×0=0$ 的贡献，所以此时容斥系数为 $1$。
• 当答案至少有 $2$ 个产生贡献时：之前产生 $\binom{2}{0}\times0+\binom{2}{1}\times1=2$ 的贡献，所以此时容斥系数为 $−2$。
• 当答案至少有 3 个产生贡献时：之前产生 $\binom{3}{0}\times0+\binom{3}{1}\times1+\binom{3}{2}\times−2=−3$ 的贡献，所以此时容斥系数为 $4$。
• 当答案至少有 3 个产生贡献时：之前产生 $\binom{4}{0}\times0+\binom{4}{1}\times1+\binom{4}{2}\times−2+\binom{4}{3}\times4=8$ 的贡献，所以此时容斥系数为 $-8$。

所以答案至少为 $x$ 时，容斥系数为 $(-2)^{x-1}$。

考虑如何计算答案：

• 只有行产生贡献时，答案是 $\sum_{i=1}^n(−2)^{i−1}\binom{n}{i}2^i2^{(n−i)m}$。具体含义为从 $n$ 行中选择 $i$ 列颜色相同，他们颜色方案数为 $2^i$。其余位置方案数为 $2^{(n−i)m}$。
• 只有列产生贡献时，答案是 $\sum_{i=1}^m(−2)^{i−1}\binom{m}{i}2^i2^{(m−i)n}$，与行同理。
• 都产生贡献时，答案是 $\sum_{i=1}^n\sum_{j=1}^m(-2)^{i+j-1}\binom{n}{i}\binom{m}{j}2\times2^{(m-i)(n-i)}$，考虑枚举行与列分别的贡献，如果列的颜色相同，行的颜色也相同，那么总的颜色只有全黑和全白两种。

对第三个式子进行优化：

$$\begin{align} f(n,m) &=\sum_{i=1}^n\sum_{j=1}^m(-2)^{i+j-1}\binom{n}{i}\binom{m}{j}2\times2^{(m-i)(n-j)}\\ &=\sum_{i=1}^n2(-2)^{i-1}\binom{n}{i}\sum_{j=1}^m(-2)^j\binom{m}{j}\times(2^{(n-i)})^{(m-j)}\\ &=\sum_{i=1}^n2(-2)^{i-1}\binom{n}{i}[(-2+2^{n-i})^m-2^{(n-i)m}] \end{align}$$

因此转移的复杂度就可以做到 $O(T(n+m)\log n)$。

T4-吃饭（eat）

题面

共有 $2\times n-1$ 个数，每个数为 $a_i$。

有一个序列 $b$，要求前 $2\times i-1$ 个数的中位数是 $b_i$。

可以任意调整 $a$ 的顺序，但是不确定序列 $b$，求有多少种序列 $b$ 可以被满足。

答案对 $1\times 10^9+7$ 取模。

$n\leq50,a_i\leq2\times n-1$

题解

先尝试找出满足 $b$ 的充要条件。简化问题，先考虑 $a_i$ 构成 $1$ 到 $2\times n−1$ 的排列的情况。

容易知道 $b_i\in[i,2\times n−i]$，因为至少有 $i−1$ 个数比 $b_i$ 小或大。同时，序列中位数从 $b_i$ 变化为 $b_i+1$ 的过程中，由于只加入 $a_{2\times i}$ 和 $a_{2\times i+1}$，所以中位数至多挪动一位。则 $a_1$ 到 $a_{2\times i−1}$ 的取值不能在 $b_i$ 与 $b_i+1$ 之间。于是可推出 $b_1$ 到 $b_i−1$ 的取值不在 $b_i$ 与 $b_i+1$ 之间。

可以证明满足这两条限制是充分的。只需要构造出合法 $a$ 序列。若 $b_i=b_i+1$，则加入目前不在序列中的最小和最大的 $a_i$。若 $b_i<b_i+1$，则若 $b_i+1$ 还不在序列中则加入 $b_i+1$ 和目前不在序列中的最大数，否则加入两个最大数。$b_i>b_i+1$ 同理。容易验证这样的构造是合法的。

接下来考虑如何 dp 求解。倒过来考虑，这时第一条限制可认为是每次解锁 $i$ 和 $2\times n−i$ 两个取值，第二条限制可认为是 $b_i$ 到 $b_i+1$ 之间的所有取值都要被删去。设 $dp_{i,j,k}$ 为已确定 $b_i$ 及之后的取值，此时还未被删去的取值中还有 $j$ 个比 $b_i$ 小，$k$ 个比 $b_i$ 大，这样的方案数。（没有必要记录具体取值，只需要记录相对位置）转移只需要考虑 $b_i−1$ 的取值，并删去 $b_i$ 与 $b_i−1$ 的之间取值，并解锁最小最大两个新取值即可。

最后解决 $a_i$ 重复的问题。这需要将每个 $b_i$ 的取值改变为在 $a$ 序列中的排名。那就希望相同的 $b_i$ 对应的排名尽量相同（少被第二条限制删掉），且尽量早地摆脱第一条限制。所以只需要判断相同取值的 $a_i$ 排名中哪一个最早摆脱第一条限制，并将所有 $b_i$ 都设为这个排名即可。于是 dp 时只需要判断新解锁的取值是否和前面重复，来决定是否对 $j$ 或 $k$ 加一。

时间复杂度 $O(n^4)$。